package fun.coding.linkedlist;

public class LinkedListManipulationImpl implements LinkedListManipulation {

	public void interpolateList(SimpleLinkedList sll) {
		Node slowNode = sll.getHead();
		Node fastNode = sll.getHead();
		
		while(fastNode != null) {
			slowNode = slowNode.getNext();
			fastNode = fastNode.getNext().getNext();
		}
		// Could use this to find the middle node of a linkedList
		Node midNode = slowNode;
		System.out.println("** midNode is " + midNode.getValue());
		Node startNode = sll.getHead();
		
		// FIXME: this logic is not correct!!
		while(midNode != null) {
			if(startNode.getValue() == slowNode.getValue()) {
				startNode.setNext(null);
			}
			Node startNodeNext = startNode.getNext();
			Node midNodeNext = midNode.getNext();
			midNode.setNext(startNode.getNext());
			startNode.setNext(midNode);
			midNode = midNodeNext;
			startNode = startNodeNext;
		}
	}

	/*
	 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
		Output: 7 -> 0 -> 8
	 * (non-Javadoc)
	 * @see interview.coding.linkedlist.LinkedListManipulation#addTwoNumbers(interview.coding.linkedlist.Node, interview.coding.linkedlist.Node)
	 */
	@Override
	public Node addTwoNumbers(Node l1, Node l2) {
		if(l1 == null && l2 == null)
			return null;
		
		int carry = 0;
		Node head = new Node();
		Node curNode = head;
		
		while(l1 != null && l2 != null) {
			int total = l1.getValue() + l2.getValue() + carry;
			int res = total % 10;
			carry = total / 10;
			
			
			Node n = new Node();
			n.setNext(null);
			n.setValue(res);
			
			curNode.setNext(n);
			curNode = n;
			
			l1 = l1.getNext();
			l2 = l2.getNext();
		}
		
		while(l1 != null) {
			int total = l1.getValue() + carry;
			int res = total % 10;
			carry = total / 10;
			
			Node n = new Node();
			n.setNext(null);
			n.setValue(res);
			
			curNode.setNext(n);
			curNode = n;
			
			l1 = l1.getNext();
		}
		
		while(l2 != null) {
			int total = l2.getValue() + carry;
			int res = total % 10;
			carry = total / 10;
			
			Node n = new Node();
			n.setNext(null);
			n.setValue(res);
			
			curNode.setNext(n);
			curNode = n;
			
			l2 = l2.getNext();
		}
		
		if(carry != 0) {
			Node n = new Node();
			n.setNext(null);
			n.setValue(1);
			
			curNode.setNext(n);
		}
		
		return head;
	}

	/* Simpley reverse a linked list without using a stack by changing the pointers.
	 * 
	 * 1 -> 2 -> 3 -> 4
	 * return 1 <- 2 <- 3 <- 4
	 * I need three pointers for this, previous, current and next. 
	 * */
	@Override
	public Node reverseLinkedList(Node head) {
	    Node current = head;
	    Node previous = null;
	    
	    while(current != null) {
	        Node next = current.getNext();
	        current.setNext(previous);
	        previous = current;
	        current = next;
	        
	    }
	    
		return previous;
	}
	
	// Swap nodes in linked list without using the copy element method.
	/* 1 -> 2 -> 3 -> 4 -> 5
	 * 2 -> 1 -> 4 -> 3 -> 5
	 * 
	 * 1
	 * 
	 * 1->2 2->1
	 * 1->2->3, 2->1->3
	 * 
	 * My microsoft onsite question. 
	 * */
	@Override
	public Node swapLinkedList(Node head) {
		if(head == null) {
			return null;
		}
		
		if(head.getNext() == null) {
			return head;
		}
		
		
		Node prev = null;
		Node cur = head;
		Node next = head.getNext();
		
		head = head.getNext();
		
		// Either one of them is null means we reach the end.
		while(next != null && cur != null) {
			cur.setNext(next.getNext());
			next.setNext(cur);
			if(prev != null) {
				prev.setNext(next);
			}
			prev = cur;
			
			cur = cur.getNext();
			if(cur != null) {
				next = cur.getNext();
			}
		}
		
	
		return head;
	}
}
